/* =========================================================================
 *
 *   Development by Sedelnikov Alexander (Bigking).
 *
 * =========================================================================
 */

#ifndef __HASH_TABLE_H__
#define __HASH_TABLE_H__


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#ifndef ushort
#define ushort unsigned short
#endif

#ifndef uint
#define uint unsigned int
#endif

#ifndef ulong
#define ulong unsigned long
#endif


//-----------------------------------------------------------------------//
//
// Fast memory allocator, working as a stack principle.
// Note: First checking by the valgrind is a no memory leak.
//
template< typename type >
class cmemory_stack
{


protected:
    type        **buffers;
    type         *cur_ptr;

    int           buffers_allocated,
                  buffer_index,
                  buffer_offset;

    int           items_per_block,
                  buffers_per_alloc;

public:
    cmemory_stack()             { buffers = NULL;    }
    ~cmemory_stack()            {                    }

    //-----------------------------------------------------------------------//
    int     create( int ipb = 0x400, int bpa = 0x10 )
    {
        if( buffers != NULL )
            release();

        items_per_block   = ipb;
        buffers_per_alloc = bpa;
        buffers_allocated = bpa;

        buffers = (type**)malloc( sizeof( type* ) * bpa );

        for( int i = 0; i < bpa; i++ )
            buffers[ i ] = (type*)malloc( sizeof( type ) * ipb );

        buffer_index  = 0;
        buffer_offset = 0;
        cur_ptr       = buffers[ 0 ] - 1;

        return 0;
    }

    //-----------------------------------------------------------------------//
    void    release()
    {
        if( buffers == NULL )
            return;

        for( int i = 0; i < buffers_allocated; i++ )
            free( buffers[ i ] );

        free( buffers );
        buffers = NULL;
    }

    //-----------------------------------------------------------------------//
    type *alloc_push( )
    {
        if( buffer_offset >= items_per_block )
        {
            buffer_index++;
            buffer_offset = 0;

            if( buffer_index >= buffers_allocated )
            {
                buffers_allocated += buffers_per_alloc;

                buffers = (type**)realloc( buffers, sizeof( type* ) * buffers_allocated );

                for( int i = buffer_index; i < buffers_allocated; i++ )
                    buffers[ i ] = (type*)malloc( sizeof( type ) * items_per_block );
            }

            cur_ptr = buffers[ buffer_index ] - 1;
        }

        buffer_offset++;
        cur_ptr++;

        return cur_ptr;
    }

    //-----------------------------------------------------------------------//
    type *free_pop( )
    {
        buffer_offset--;
        cur_ptr--;

        if( buffer_offset <= 0 )
        {
            buffer_index--;
            buffer_offset = items_per_block;

            if( buffer_index < 0 )
            {
                buffer_index  = 0;
                buffer_offset = 0;
                cur_ptr       = buffers[ 0 ] - 1;
                return NULL;
            }

            if( buffer_index + buffers_per_alloc < buffers_allocated )
            {
                for( int i = buffers_allocated - 1;
                    i > buffer_index;
                    i-- )
                    free( buffers[ i ] );

                buffers_allocated = buffer_index + 1;
                buffers = (type**)realloc( buffers, sizeof( type* ) * buffers_allocated );
            }

            cur_ptr = buffers[ buffer_index ] + items_per_block - 1;
        }

        return cur_ptr;
    }
};




//-----------------------------------------------------------------------//
//
// Hash table with event function (on dublicate founded).
//
template< typename type >
class chash_table : public cmemory_stack< type >
{


protected:

    //-----------------------------------------------------------------------//
    struct chash_table_entry
    {
        type                   *data;
        chash_table_entry      *next;
    };

    int                         count;

    ulong                       hash_size;
    chash_table_entry         **hash_table;

    cmemory_stack<chash_table_entry>         memory_hash_table;

public:


    //-----------------------------------------------------------------------//
    chash_table()       {   hash_table = NULL;    }
    chash_table( int hash_size, int items_start_allocated )
    {   hash_table = NULL; create( hash_size, items_start_allocated );    }
    ~chash_table()      {       }

    //-----------------------------------------------------------------------//
    ulong size()
    {
        return count;
    }

    //-----------------------------------------------------------------------//
    int create( int hash_size, int items_start_allocated )
    {
        if( hash_table != NULL )
            release();

        memory_hash_table.create( hash_size / 2, 6 );
        if( cmemory_stack<type>::create( items_start_allocated ) != 0 )
            return 1;

        count           = 0;
        this->hash_size = hash_size;

        hash_table = new chash_table_entry*[ hash_size ];
        memset( hash_table, 0, sizeof( chash_table_entry* ) * hash_size );

        return 0;
    }

    //-----------------------------------------------------------------------//
    int  add( const type &t )
    {
        ulong       hash = (!t) % hash_size;

        // check on free
        if( hash_table[ hash ] == NULL )
        {
            hash_table[ hash ] = memory_hash_table.alloc_push();
            hash_table[ hash ]->data = cmemory_stack<type>::alloc_push( );
            hash_table[ hash ]->next = NULL;
            *hash_table[ hash ]->data = t;
            count++;
            return 0;
        }

        // search duplicates and free space
        chash_table_entry *hash_ptr = hash_table[ hash ], *hash_ptr_prev;
        while( hash_ptr != NULL )
        {
            hash_ptr_prev = hash_ptr;

            if( *hash_ptr->data == t )
            {
                *hash_ptr->data += t;
                return 0;
            }

            hash_ptr = hash_ptr->next;
        }

        // allocate new object if duplicate not founded
        hash_ptr = memory_hash_table.alloc_push() ;
        hash_ptr->data = cmemory_stack<type>::alloc_push( );
        hash_ptr->next = NULL;
        *hash_ptr->data = t;
        hash_ptr_prev->next = hash_ptr;
        count++;

        return 0;
    }

    //-----------------------------------------------------------------------//
    void release( )
    {
        if( hash_table == NULL )
            return;

        delete []hash_table;
        hash_table = NULL;

        memory_hash_table.release();
        cmemory_stack<type>::release();
    }

    //-----------------------------------------------------------------------//
    //-----------------------------------------------------------------------//
    //-----------------------------------------------------------------------//
    friend  class iterator;

    class iterator
    {


        int                  buf_i;
        int                  buf_o;
        type                *ptr;
        chash_table<type>   *base;
    public:

        //-----------------------------------------------------------------------//
        iterator()
        {
            ptr = NULL;
        }

        //-----------------------------------------------------------------------//
        void operator=( chash_table<type> &table )
        {
            buf_i = 0;
            buf_o = 0;
            ptr   = table.buffers[ 0 ];
            base  = &table;

            if( base->size() == 0 )
                ptr = NULL;
        }

        //-----------------------------------------------------------------------//
        operator bool() const
        {
            return ptr != NULL;
        }

        //-----------------------------------------------------------------------//
        void operator++( int val )
        {
            ptr++;
            buf_o++;

            if( buf_i == base->buffer_index &&
                buf_o >= base->buffer_offset )
            {
                ptr = 0;
                return;
            }

            if( buf_o >= base->items_per_block )
            {
                buf_o = 0;
                buf_i++;

                if( buf_i == base->buffer_index &&
                    buf_o >= base->buffer_offset )
                {
                    ptr = 0;
                    return;
                }

                ptr = base->buffers[ buf_i ];
            }
        }

        //-----------------------------------------------------------------------//
        operator type()
        {
            return *ptr;
        }

        //-----------------------------------------------------------------------//
        type* operator->()
        {
            return ptr;
        }


    };


};


#endif
